/*
 * This section is intended to be used only in mathematical problems. However, it
 * may be used also in problem solutions of other nature.
 *
 * Instead of the application of a void pointer is possible to use inheritance to
 * solve the problem. We can state that polynomial and a variable class must have
 * the same parent class like general_polynomial.
 * It is mandatory to overload the arithmetical operators and between all child classes.
 */
#include "polynomial.h"
#include<algorithm>
//For debugg purposes
#include<iostream>
//Construtctors
template<typename T>
polynomial<T>::polynomial(std::vector<std::string> vrs){
    term t(new std::string(vrs),"string");
    vars.push_back(t);
}  //To identify the ring this polynomial belongs to

template<typename T>
polynomial<T>::polynomial(std::vector<std::string> vrs, T coeff){
    T zt(0);
    if(coeff!=zt){
        typename std::vector<std::string>::iterator it = vrs.begin();
        for(;it!=vrs.end();++it){
            term t(new std::string(*it),"string");
            vars.push_back(t);
        }
        std::vector<int> tmp;  //A polynomial is more generic than a ring or field element
        if(!vrs.empty()){
            tmp.push_back(0);
        }
        ht[tmp] = coeff;
    }
}
template<typename T>
polynomial<T>::polynomial(std::vector<std::string> vrs, std::vector<int> degree, T coeff){
    if(vrs.size()<degree.size()) throw polynomial_exception();
    T zt(0);
    if(coeff!=zt){
        typename std::vector<std::string>::iterator it = vrs.begin();
        for(;it!=vrs.end();++it){
            term t(new std::string(*it),"string");
            vars.push_back(t);
        }
        ht[degree]=coeff;
    }
}
//The copy contructor is quite simple
template<typename T>
polynomial<T>::polynomial(const polynomial& right):ht(right.ht),vars(right.vars){
}
//------------------------------------------------------
//-------------Public functions-------------------------
//------------------------------------------------------
template<typename T>
polynomial<T> polynomial<T>::add(polynomial<T> right){
    polynomial<T> res;
    typename std::vector<term>::iterator vars_it = vars.begin();
    for(;vars_it!=vars.end();++vars_it){
        res.vars.push_back(*vars_it);
    }
    for(vars_it=right.vars.begin();vars_it!=right.vars.end();++vars_it){
        bool found=false;
        typename std::vector<term>::iterator vars_it_temp = res.vars.begin();
        for(;vars_it_temp!=res.vars.end();++vars_it_temp){
            if((*vars_it)==(*vars_it_temp)){
                found=true;
                break;
            }
        }
        if(!found){
            res.vars.push_back(*vars_it);
        }
    }
    //At this point, the res vector has a merged list of variables
    typename std::map<std::vector<int>,T>::iterator map_it = ht.begin();
    std::map<std::vector<int>,T> map_temp(right.ht);  //To support a copy of the second term
    for(;map_it!=ht.end();++map_it){
        std::vector<int> vec_degree;
        vec_degree.clear();
        //Try to find an equal term at right side
        typename std::map<std::vector<int>,T>::iterator map_it_temp = map_temp.begin();
        for(;map_it_temp!=map_temp.end();++map_it_temp)
            if(compare_term(vars,map_it->first,right.vars,map_it_temp->first)) break;
        if(map_it_temp!=map_temp.end()){
            res.ht[map_it->first]=(map_it->second)+(map_it_temp->second);
            //Remove the redundant term in right side
            map_temp.erase(map_it_temp);
        }
        else{
            res.ht[map_it->first]=map_it->second;
        }
    }
    std::vector<int> insert_degree;
    //At this point all repeated terms were eliminated from map_temp
    for(map_it=map_temp.begin();map_it!=map_temp.end();++map_it){
        //Construct the correspondent degree to insert in the hash table
        insert_degree.clear();
        for(int i=0;i<res.vars.size();++i){
            bool found=false;
            int j=0;
            for(j=0;j<right.vars.size();++j){
                if(res.vars[i]==right.vars[j]){
                    found=true;
                    break;
                }
            }
            if(found){
                insert_degree.push_back(j<(map_it->first).size()?(map_it->first)[j]:0);
            }
            else{
                insert_degree.push_back(0);
            }
        }
        res.ht[insert_degree]=map_it->second;
    }
    return res;
}


template<typename T>
polynomial<T> polynomial<T>::multiply(polynomial<T> right){
    polynomial<T> res;
    typename std::map<std::vector<int>,T>::iterator it = ht.begin();
    for(;it!=ht.end();++it){
        typename std::map<std::vector<int>,T>::iterator it1 = right.ht.begin();
        for(;it1!=right.ht.end();++it1){
            polynomial res_temp = res.add(multiply_term(vars,it->first,it->second,right.vars,it1->first,it1->second));
            //std::cout<<multiply_term(vars,it->first,it->second,right.vars,it1->first,it1->second);
            //std::cout<<std::endl;
            res = res_temp;
        }
    }
    return res;
}

template<typename T>
polynomial<T> polynomial<T>::power(int n){
    T init(1);
    std::vector<int> degree;
    polynomial res;
    for(int i=0;i<vars.size();++i)
        res.vars.push_back(vars[i]);
    std::vector<int> vec_int;
    res.ht[vec_int]=init;
    if(n==0) return res;
    if(n<0) throw polynomial_exception();
    res = *this;
    int r = n % 2 ;
    int q = n / 2;
    while(q!=0){
        polynomial res_temp = res.multiply(res);
        res = res_temp;
        if(r!=0){
            polynomial res_temp1 = res.multiply(*this);
            res = res_temp1;
        }
        r = q % 2;
        q = q / 2;
    }
    return res;
}

template<typename T>
polynomial<T> polynomial<T>::substitute_var(std::string var_to_subs, polynomial<T> new_var){
    //std::vector<term> vrs;
    //typename std::vector<term>::iterator it = vars.begin();
    polynomial<T> p;
    term t_to_subs(new std::string(var_to_subs),"string");
    term t_subs(new polynomial(new_var),"polynomial");
    for(int i=0;i<vars.size();i++){
        if(t_to_subs==vars[i]){
            p.vars.push_back(t_subs);
        }
        else{
            p.vars.push_back(vars[i]);
        }
    }
    p.ht = ht;
    return p;
}

template<typename T>
polynomial<T> polynomial<T>::substitute_var(std::string var_to_subs, std::string new_var){
    polynomial<T> p;
    term t_to_subs(new std::string(var_to_subs),"string");
    term t_subs(new std::string(new_var),"string");
    for(int i=0;i<vars.size();i++){
        if(t_to_subs==vars[i]){
            p.vars.push_back(t_subs);
        }
        else{
            p.vars.push_back(vars[i]);
        }
    }
    p.ht = ht;
    return p;
}

template<typename T>
polynomial<T> polynomial<T>::expand(){
    polynomial<T> res;
    typename std::map<std::vector<int>,T>::iterator it = ht.begin();
    for(;it!=ht.end();++it){
        polynomial temp = res.add(expand_term(vars,it->first,it->second));
        //std::cout<<"temp="<<expand_term(vars,it->first,it->second)<<" at cicle in expand function"<<std::endl;
        res = temp;
    }
    //std::cout<<"res="<<res<<" at expand function"<<std::endl;
    return res;
}

template<typename T>
int polynomial<T>::degree(){ 
}

template<typename T>
int polynomial<T>::degree_var(std::string vr){
    int res = 0;
    typename std::map<std::vector<int>,T>::iterator ht_iterator;
    typename std::vector<term>::iterator vars_iterator;
    //Determine the correspondent degree
    for(ht_iterator=ht.begin();ht_iterator!=ht.end();++ht_iterator){
        int temp=0;
        int count=0;
        for(vars_iterator=vars.begin();vars_iterator!=vars.end();++vars_iterator){
            if((*vars_iterator).get_term_type()=="string"){
                std::string* str_pointer=(std::string*)(*vars_iterator).get_term_pointer();
                if(*str_pointer==vr){
                    int deg=(ht_iterator->first).size()>count?(ht_iterator->first)[count]:0;
                    temp += deg;
                }
            }
            else if((*vars_iterator).get_term_type()=="polynomial"){
                polynomial<T>* pol_pointer = (polynomial*)(*vars_iterator).get_term_pointer();
                int deg=(ht_iterator->first).size()>count?(ht_iterator->first)[count]:0;
                temp += deg*pol_pointer->degree_var(vr);
            }
            count++;
        }
        if(temp>res) res=temp;
    }
    return res;
}
//-------------------------------------------------------
//-----------------Operator overload---------------------
//-------------------------------------------------------
template<typename T>
polynomial<T> polynomial<T>::operator+(polynomial<T>& right){
    return add(right);
}

template<typename T>
polynomial<T> polynomial<T>::operator-(polynomial<T>& right){
    T symm_unit(-1);  //Or something like the symmetric
    polynomial temp(symm_unit);
    return add(right.multiply(temp));
}

template<typename T>
polynomial<T> polynomial<T>::operator*(polynomial<T>& right){
   return multiply(right);
}

//it is possible to define / operator based on ideals and normal forms
//If we devide p polynomial with q polynomial we calculate the normal form
//of p with respect to <q> - postponed 

template<typename T>
polynomial<T>& polynomial<T>::operator=(polynomial<T>& right){
    ht=right.ht;
    vars.clear();
    typename std::vector<term>::iterator it = right.vars.begin();
    for(;it!=right.vars.end();++it){
        vars.push_back(*it);
    }
    return *this;
}

template<typename T>
bool polynomial<T>::operator==(polynomial<T>& right){
}

template<typename T>
bool polynomial<T>::operator!=(polynomial<T>& right){
}

//---------------------------------------------------------
//----------------Friend operators-------------------------
//---------------------------------------------------------
template<typename R>
std::istream& operator>>(std::istream& is, polynomial<R>& p){
}

template<typename R>
std::ostream& operator<<(std::ostream& os, polynomial<R> p){
    p.write(os);
    return os;
}
//---------------------------------------------------------
//------------------Private Functions definition-----------
//---------------------------------------------------------
template<typename T>
polynomial<T> polynomial<T>::multiply_term(std::vector<term> vrs1, std::vector<int> deg1, T coeff1, 
                                                std::vector<term> vrs2, std::vector<int> deg2, T coeff2){
    std::map<std::vector<int>,T> ht_res;
    std::vector<term> vrs_res;
    std::vector<int> deg_temp;
    int tmp1, tmp2;
    for(int i=0;i<vrs1.size();++i){
        bool found=false;
        for(int j=i;j<vrs2.size();++j){
            if(vrs1[i]==vrs2[j]){
                tmp1=i<deg1.size()?deg1[i]:0;
                tmp2=i<deg2.size()?deg2[j]:0;
                vrs_res.push_back(vrs1[i]);
                deg_temp.push_back(tmp1+tmp2);
                found=true;
            }
            else{
                bool found_first=false;
                for(int k=0;k<vrs1.size();k++){
                    if(vrs2[j]==vrs1[k]){
                        found_first=true;
                        break;
                    }
                }
                if(!found){
                    tmp2=j<deg2.size()?deg2[j]:0;
                    vrs_res.push_back(vrs2[j]);
                    deg_temp.push_back(tmp2);
                }
                /*tmp1=i<deg1.size()?deg1[i]:0;
                if(tmp1>0){
                    vrs_res.push_back(vrs1[i]);
                    deg_temp.push_back(tmp1);
                }
                tmp2=i<deg2.size()?deg2[j]:0;
                if(tmp2>0){
                    vrs_res.push_back(vrs2[j]);
                    deg_temp.push_back(tmp2);
                }*/
            }
        }
        if(!found){
            tmp1=i<deg1.size()?deg1[i]:0;
            vrs_res.push_back(vrs1[i]);
            deg_temp.push_back(tmp1);
        }
    }
    if(vrs1.empty()){
        if(vrs2.empty()){
            polynomial p;
            p.ht[deg1]=coeff1*coeff2;
        }
        polynomial q;
        for(int i=0;i<vrs2.size();++i){
            q.vars.push_back(vrs2[i]);
        }
        q.ht[deg2]=coeff1*coeff2;
        return q;
    }
    //At this point it is possible to multiply the coefficients
    polynomial<T> res;
    T zt(0);
    if(coeff1==zt || coeff2==zt) return res;
    ht_res[deg_temp]=coeff1*coeff2;
    res.ht=ht_res;
    //res.vars=vrs_res;
    typename std::vector<term>::iterator ul = vrs_res.begin();
    for(;ul!=vrs_res.end();++ul){
        res.vars.push_back(*ul);
    }
    return res;
}

template<typename T>
polynomial<T> polynomial<T>::expand_term(std::vector<term> vrs, std::vector<int> deg, T coeff){
    T un(1);
    polynomial<T> res(un);
    
    T zt(0);
    if(vrs.empty()||coeff==zt) return res;
    if(deg.empty()){
        std::map<std::vector<int>,T> ht_temp;
        ht_temp[deg]=coeff;
        res.ht=ht_temp;
        return res;
    }
    for(int i=0;i<vrs.size();++i){
        if(vrs[i].get_term_type()=="string"){
            std::vector<int> vec;
            std::vector<std::string> vec_vars;
            vec_vars.push_back(*(std::string*)vrs[i].get_term_pointer());
            vec.push_back(i<deg.size()?deg[i]:0);
            polynomial res_temp(vec_vars,vec,coeff);
            polynomial res_temp_1=res.multiply(res_temp);
            res=res_temp_1;
        }
        else if(vrs[i].get_term_type()=="polynomial"){
            polynomial* pol_pointer = (polynomial*)vrs[i].get_term_pointer();
            polynomial res_temp = pol_pointer->expand();
            polynomial res_temp1 = res_temp.power(i<deg.size()?deg[i]:0);
            polynomial res_temp2 = res.multiply(res_temp1);
            res = res_temp2;
        //Multiply the coefficient in the polynomial
        }
    }
    return res;
}

template<typename T>
std::vector<std::string> polynomial<T>::get_all_string_vars(){
    std::vector<std::string> res;
    for(int i=0;i<vars.size();++i){
        if(vars[i].get_type()=="string"){
            bool flag=false;
            for(int j=0; j<res.size();j++){
                if(vars[i]==res[j]){
                    flag=true;
                    break;
                }
            }
            if(!flag){
                std::string* str_pointer = vars[i].get_term_pointer();
                res.push_back(*str_pointer);
            }
        }
        else if(vars[i].get_type()=="polynomial"){
            polynomial<T>* pol_pointer = vars[i].get_term_pointer();
            res=merge_vars(res,pol_pointer->get_all_string_vars());
        }
    }
    return res;
}
              
template<typename T>
std::vector<std::string> polynomial<T>::merge_vars(std::vector<std::string> vrs1, 
                                                   std::vector<std::string> vrs2){
    std::vector<std::string> res;
    for(int i=0;i<vrs1.size();++i){
        res.push_back(vrs1[i]);
    }
    for(int j=0;j<vrs2.size();++j){
        bool flag=false;
        for(int k=0;k<res.size();++k){
            if(vrs2[j]==res[k]){
                flag=true;
                break;
            }
        }
        if(!flag){
            res.push_back(vrs2[j]);
        }
    }
    return res;
}

template<typename T>
bool polynomial<T>::compare_term(std::vector<term> vrs1, std::vector<int> deg1, 
                                                   std::vector<term> vrs2, std::vector<int> deg2){
    int deg_temp1, deg_temp2;
    std::vector<term>* vrs1_pointer, *vrs2_pointer;
    if(vrs1.size()>=vrs2.size()){
        vrs1_pointer=&vrs1;
        vrs2_pointer=&vrs2;
    }
    else{
        vrs1_pointer=&vrs2;
        vrs2_pointer=&vrs1;
    }
    for(int i=0;i<vrs1_pointer->size();++i){
        int j;
        for(j=i;j<vrs2_pointer->size();++j){
            if((*vrs1_pointer)[i]==(*vrs2_pointer)[j]){
                deg_temp1=i<deg1.size()?deg1[i]:0;
                deg_temp2=i<deg2.size()?deg2[j]:0;
                if(deg_temp1!=deg_temp2) return false;
                break;
            }
        }
        if(j>=vrs2_pointer->size()){
            deg_temp1=i<deg1.size()?deg1[i]:0;
            if(deg_temp1!=0) return false;
        }
    }
    return true;
}

template<typename T>
bool polynomial<T>::compare_degrees(std::vector<int> deg1, std::vector<int> deg2){
    std::vector<int>* deg1_pointer, *deg2_pointer;
    if(deg1.size()<=deg2.size()){
        deg1_pointer=&deg1;
        deg2_pointer=&deg2;
    }
    else{
        deg1_pointer=&deg2;
        deg2_pointer=&deg1;
    }
    for(int i=0;i<deg1_pointer->size();++i){
        if((*deg1_pointer)!=(*deg2_pointer)) return false;
    }
    for(int j=deg1_pointer->size();j<deg2_pointer->size();++j){
        if((*deg2_pointer)[j]!=0) return false;
    }
    return true;
}

template<typename T>
bool polynomial<T>::search_degree(typename std::map<std::vector<int>,T>::iterator map_iterator_begin,
                                  typename std::map<std::vector<int>,T>::iterator map_iterator_end, 
                                           std::vector<int> deg){
    for(;map_iterator_begin!=map_iterator_end;++map_iterator_begin){
        if(compare_degrees(map_iterator_begin->first,deg)) return true;
    }
    return false;
}

template<typename T>
std::istream& polynomial<T>::read(std::istream& is){
}

template<typename T>
std::ostream& polynomial<T>::write(std::ostream& os){
    if(ht.empty()){
        os<<"0";
        return os;
    }
    T zt(0);  //To compare with zero
    T ut(1);  //To avoid unity writing when unnecessary
    bool flag_parcel = true;  //To test if all parcels are zero until final (rare to happen)
    bool flag_term = true;  //To test if all terms have zero degree
    bool need_point = false;  //To inform the next cicle that there is a need to insert a point
    int vars_count=0;
    typename std::map<std::vector<int>,T>::iterator ht_iterator = ht.begin();
    //Initializing the cicle in the exterior in order to append a plus sign if there are other parcels
    if(ht_iterator->second==zt){
        if(ht_iterator==ht.end())
            if(flag_parcel) os<<zt;
    }
    else{
        flag_parcel = false;
        flag_term = true;
        if(ht_iterator->second!=ut){
            os<<ht_iterator->second;
            flag_term = false;
        }
        for(vars_count=0;vars_count<vars.size();vars_count++){
            int term_degree = vars_count<(ht_iterator->first).size()?(ht_iterator->first)[vars_count]:0;
            if(term_degree!=0){
                if(need_point){
                    os<<".";
                    need_point=false;
                }
                vars[vars_count].write(os);
                if(term_degree!=1){
                    os<<"^"<<term_degree;
                }
                else need_point=true;
                flag_term=false;
            }
            else{
                if(vars_count>=vars.size()-1){
                    if(flag_term) os<<ut;  //Print the unity if all variable degrees are null
                }
            }
        }
    }
    ++ht_iterator;
    for(;ht_iterator!=ht.end();++ht_iterator){
        if(ht_iterator->second==zt){
            if(ht_iterator==ht.end())
                if(flag_parcel) os<<zt;
        }
        else{
            flag_parcel = false;
            flag_term = true;
            need_point = false;
            bool need_plus = true;
            if(ht_iterator->second!=ut){
                os<<"+"<<ht_iterator->second;
                need_plus = false;
                flag_term = false;
            }
            for(vars_count=0;vars_count<vars.size();vars_count++){
                int term_degree = vars_count<(ht_iterator->first).size()?(ht_iterator->first)[vars_count]:0;
                if(term_degree!=0){
                    if(need_plus){
                        os<<"+";
                        need_plus = false;
                    }
                    if(need_point){
                        os<<".";
                        need_point=false;
                    }
                    vars[vars_count].write(os);
                    if(term_degree!=1){
                        os<<"^"<<term_degree;
                    }
                    else need_point=true;
                    flag_term=false;
                }
                else{
                    if(vars_count==vars.size()-1){
                        if(flag_term) os<<"+"<<ut;  //Print the unity if all variable degrees are null
                    }
                    need_point=true;
                }
            }
        }
    }
    return os;
}
